package 剑指offer;


/*
 * Author：江松
 * Date：2023/3/19 13:32
 *
 注意特殊情况：路径比地图还大，长度为1时（不特判，用代码统一这种情况）
 */

public class Main44 {


    private boolean vis[][];
    private int n,m,len;
    private boolean ans;
    private char[][] map;
    private char []str;

     int dx[]={1,-1,0,0};
     int dy[]={0,0,1,-1};

    public void dfs(int x,int y,int now){
        if(str[now]!=map[x][y])return;
        if(now+1==len){
            ans=true;
            return;
        }

        System.out.printf("(%d,%d)--%d\n",x,y,now);
        //朝着4个方向搜索
        for(int i=0;i<4;++i){
            int xx=x+dx[i];
            int yy=y+dy[i];
            if(xx>=0&&xx<n&&yy>=0&&yy<m&&!vis[xx][yy]){
                vis[xx][yy]=true;
                dfs(xx,yy,now+1);
                vis[xx][yy]=false;
            }
        }
    }

    public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
        if(matrix==null||matrix.length==0)return false;
        if(rows==0||cols==0)return false;
        //初始化
        vis=new boolean[rows][cols];
        map=new char[rows][cols];
        this.str=str;
        n=rows;m=cols;len=str.length;
        for(int i=0;i<rows;++i){
            for(int j=0;j<cols;++j){
                map[i][j]=matrix[cols*i+j];
            }
        }

        System.out.println("***");
        for(int i=0;i<n;++i){
            for(int j=0;j<m;++j){
                if(map[i][j]==str[0]){

                    vis[i][j]=true;
                    dfs(i,j,0);
                    if(ans)return true;
                    vis[i][j]=false;
                }
            }
        }

        return false;
    }
}
